import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * 冒泡排序法
 * 冒泡排序通过重复地遍历待排序的列表，比较相邻的元素并交换它们的位置来实现排序。
 * 该算法的名称来源于较小的元素会像"气泡"一样逐渐"浮"到列表的顶端。
 * 算法的每一轮都可以确定一个元素的最终位置。
 * 最优情况：
 * 当输入的数据已经是正序时：O(N)
 * 最坏情况：
 * 当输入的数据是反序时：O(n²)
 *
 * @author Liu Yicong
 * @date 2025/9/21
 */
public class BubbleSort {

	public static Integer[] bubbleSort(Integer[] arr) {
		int n = arr.length;
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < n - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					int t = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = t;
				}
			}
		}
		return arr;
	}

	public static Integer[] optBubbleSort(Integer[] arr) {
		int n = arr.length;
		for (int i = 0; i < n - 1; i++) {
			boolean swaped = false;
			for (int j = 0; j < n - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					int t = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = t;
					swaped = true;
				}
			}
			if (!swaped) {
				break;
			}
		}
		return arr;
	}


	public static void main(String[] args) {
		// 读取数据
		Scanner sc = new Scanner(System.in);
		String input = sc.nextLine();
		sc.close();
		// 将读取的文字转换为一个整数集合
		String[] strs = input.split(" ");
		List<Integer> arr = Arrays.stream(strs).map(Integer::valueOf).collect(Collectors.toList());

		List<Integer> res = Arrays.asList((bubbleSort(arr.toArray(new Integer[0]))));
		System.out.println(res);

		res = Arrays.asList((optBubbleSort(arr.toArray(new Integer[0]))));
		System.out.println(res);
	}
}
